package sysu.el.graph.undi.algor;

import sysu.el.array.TagArray;
import sysu.el.array.ints.ArrInt;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.graph.GTAdjList;
import sysu.el.graph.undi.UndiGTAdjList;

public class UndiBFSTagAlgor{

	/* ******************************************************************** */
	/* ************************* Attribute op ***************************** */
	/* ******************************************************************** */
	/**
	 * These two attributes decide the class
	 */
	protected TagArray tag;
	protected ArrQueueInt queue;
	/* ******************************************************************** */
	/* ************************* Constructors ***************************** */
	/* ******************************************************************** */
	public UndiBFSTagAlgor(int len){
		queue = new ArrQueueInt(len);
		tag = new TagArray(len);
	}
	
	
	// Functor State Parameters
	public int curStartNode;
	protected UndiGTAdjList adjList;
	protected int curTag;
	
	public ArrInt[] getSetsWithTags(){
		return tag.getElemsWithTag();
	}

	/* ******************************************************************** */
	/* ************************* Essential OP ***************************** */
	/* ******************************************************************** */
	public void bfs(int num, int searchHeads[], UndiGTAdjList gTAdjList){
		tag.reset(num);
		for (int i=0; i<num; i++){
			this.curTag = i;
			bfsLite(searchHeads[i], gTAdjList);
		}
	}

	public void bfs(int startNode, UndiGTAdjList gTAdjList){
		tag.reset(1);
		this.curTag = 0;
		bfsLite(startNode, gTAdjList);
	}

	public void bfs(UndiGTAdjList gTAdjList){
		tag.reset(1);
		this.curTag = 0;
		for (int i=0; i<gTAdjList.getNodeNum(); i++){
			bfsLite(i, gTAdjList);
			if (queue.getTail()>0)
				curTag ++;
		}
		curTag --;
		tag.setMaxTag(curTag);
	}

	/* ******************************************************************** */
	/* ************************* Auxiliary OP ***************************** */
	/* ******************************************************************** */

	private void addToBFSQueue(int node){
		if (tag.getTag(node) == TagArray.UnTagValue){
			queue.add(node);
			tag.setTag(node, curTag);
		}
	}

	/**
	 * Override this function, but don't forget to invoke super(), 
	 * unless you got different ideas.
	 */
	public void setup(){
		queue.reset();
		this.addToBFSQueue(this.curStartNode);
	}
	
	public void bfsLite(int startNode, UndiGTAdjList gTAdjList){
		this.curStartNode = startNode;
		this.adjList = gTAdjList;
		this.bfsLite();
	}
	
	public void bfsLite(){
		this.setup();
		while (queue.isNotEmpty()){
			int h = queue.forward();
			int list[] = this.adjList.getList(h);
			int counter = this.adjList.getDegree(h)-1;
			while (counter >= 0){
				int elem = list[counter];
				this.addToBFSQueue(elem);
				counter --;
			} // End While
		} // End While
	}
}
